package com.tgy.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author: tgy
 * @Date: 1/13/21 9:54 AM
 *
 *  https://leetcode-cn.com/problems/merge-k-sorted-lists/
 *
 *  n:平均每个链表度长度
 *  k: 链表个数
 *  时间复杂度: O(nklogk)
 *  空间复杂的: O(k)
 */
public class _23_合并K个升序链表_堆 {

    public ListNode mergeKLists(ListNode[] lists) {

//        dummy

        if (lists == null || lists.length == 0) {

            return null;
        }

        if (lists.length == 1) {
            return lists[0];
        }

        ListNode dummyNode = new ListNode();
        ListNode tail = dummyNode;

        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {

                return Integer.compare(o1.val,o2.val);
            }
        });

        for (ListNode list : lists) {

            if (list != null) {
                queue.offer(list);
            }
        }

        while (!queue.isEmpty()) {


            ListNode node = queue.poll();

            if (node.next != null) {

                queue.offer(node.next);
            }

            tail.next = node;
            tail = node;
        }

        return dummyNode.next;
    }


}
